闲话

这场的$E$差点科技树,之后补.这场VP也打得很惨烈,就出了AB,B还写的特别难受,C也是想到写法也不想动,真的难写.这场ABC感觉没啥思维,就敲.

A. Filling Shapes

题目大意:有一个$3*n$的棋盘,给你一个成三角状的棋子,问有多少种方法填满整个棋盘.

数据范围: $1 \leq n \leq 60$

思路

由于行数已经确定了,这导致每一列都一定是两个三角棋子拼起来的,一个占两位一个占一位.进一步的,每一个$2*3$的部分都是由两个三角棋子拼起来的,一共需要$n/2$个这样的组合体,每个组合体有$2$种拼法.因此当$n$是奇数的时候无解,反之答案为$2^{n/2}$

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	int n;scanf("%d",&n);
	if(n % 2 == 0)	
	{
		int c = n / 2;
		printf("%d",(1 << c));
	}
	else printf("0");
    return 0;
}

B. Plus from Picture

题目大意:有一个$w*h$大小的图片,上面有颜色的部分标记为*,没有的标记为..问图上是否存在一个呈加号模样颜色块.
注意:必须只有一个,除了这个加号之外不能有任何颜色,这个加号可以不是对称或是循环相等的.但是必须要有四个棱,以及一个中心,且不能错位或没有.

数据范围:
$1 \leq w,h \leq 500$

思路

典型的模拟题,vp的时候快写吐了.简单的实现方法是,因为仅仅只能有一个加号,所以我只要找到一个边角四位都是*的颜色点,以他为中心向四个方向拓展,注意是连续的拓展,那么拓展完之后如果整张图上还有颜色块,那么就无解.如果一开始连一个有四个方向相连的颜色块都没有,也无解.若都不满足,则说明有解.
闲话:我开始的想法是先$dfs$找联通块,找完了再找边角的颜色块的坐标,再删元素,就非常麻烦而且难以保证正确性.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 505;
char g[N][N];
int n,m;
const int dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i)	scanf("%s",g[i] + 1);
	bool find = 0;

	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
		{
			if(g[i][j] == '*' && !find)
			{
				bool ok = 1;
				for(int _ = 0;_ < 4;++_)
					if(g[i + dx[_]][j + dy[_]] != '*')
						ok = 0;
				if(!ok)	continue;
				find = 1;
				int x = i,y = j;
				while(g[x][y - 1] == '*')	g[x][--y] = '#';
				y = j;
				while(g[x][y + 1] == '*')	g[x][++y] = '#';
				y = j;
				while(g[x - 1][y] == '*')	g[--x][y] = '#';
				x = i;
				while(g[x + 1][y] == '*')	g[++x][y] = '#';
				g[i][j] = '#';
			}
		}
	if(!find)	
	{
		puts("NO");
		return 0;
	}
	int ok = 1;
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
			if(g[i][j] == '*')
				ok = 0;
	if(!ok)	puts("NO");
	else puts("YES");
    return 0;
}

C. Beautiful Lyrics

题目大意:给定一个字符串集合,他有$n$个字符串,现规定一首诗的组成:
①一首诗由四个字符串组成.
②这四个字符串形式为:

a    b
c    d

③要求$a$和$c$的元音字母的数量相同,$b$和$d$的元音字母数量相同.
④$b$和$d$的最后一位元音字母也必须相同.
问从给定的集合里选出若干个字符串,最多能构造出多少种诗,输出数量以及具体方案.如果集合里有重复的元素,那么只要使用次数不超过集合里有的次数就可以了,不需要保证$a,b,c,d$都是不同的.

数据范围:
$1 \leq n 10^5$
$1 \leq \sum|S_i| \leq 10^6$
保证每个字符串$S_i$至少有一个元音字母,且长度总和不超过$10^6$

思路

为了描述方便,先规定两种字符串:
①完全相同:元音个数相同,且最后一位元音也相同.
②半相同:元音个数相同.
显然一个完全相同的也满足半相同,反过来不成立.那么原来的问题实际上就是在整个序列里寻找这样的两种方案:①两个半相同的和两个完全相同的.②四个完全相同的.显然贪心地构造:优先选择半相同和完全相同的组合,如果还剩下有多的完全相同的,则把剩下的按四个拆.
之后就是统计信息的问题:比较容易想到应该侧重于记录完全相同的.这里用$map$统计,首先要知道元音字符的个数,其次要知道最后一位元音是谁,以及满足前两个条件的所有的字符串的集合,因此$map$的定义就如下:map<int,map<char,vector<string>>> complist.在具体查找的时候,先查所有可以配在一起的完全相同字符串组合,再查剩下的所有的字符串,没有组合上的就是半相同的了.这题实现也挺麻烦的,剩下的看代码罢.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string,string> pss;
vector<string> a;
map<int,map<char,vector<string>>> complist;
inline int countv(string& s)
{
	int res = 0,n = s.size();
	for(int i = 0;i < n;++i)
		if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
			++res;
	return res;
}
inline char glastv(string& s)
{
	int n = s.size();
	for(int i = n - 1;i >= 0;--i)
		if(s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u')
			return s[i];
	return 'a';
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;
	for(int i = 0;i < n;++i)
	{
		string s;cin >> s;
		a.push_back(s);
		int cnt = countv(s);
		char last = glastv(s);
		complist[cnt][last].push_back(s);
	}
	vector<pss> comv,h_comv;
	for(auto& __t : complist)
	{
		int cnt = __t.first;auto& cache = __t.second;
		for(auto& t : cache)
		{
			char last = t.first;auto& v = t.second;
			while(v.size() >= 2)
			{
				string a = v.back();v.pop_back();
				string b = v.back();v.pop_back();
				comv.push_back({a,b});
			}
		}
		vector<string> remain;
		for(auto& t : cache)
		{
			char last = t.first;auto& v = t.second;
			for(auto& s : v)	remain.push_back(s);
			v.clear();
		}
		while(remain.size() >= 2)
		{
			string a = remain.back();remain.pop_back();
			string b = remain.back();remain.pop_back();
			h_comv.push_back({a,b});
		}
	}
	
	vector<pss>	res;
    while(!comv.empty() && !h_comv.empty())
    {
    	pss a = comv.back();comv.pop_back();
    	pss b = h_comv.back();h_comv.pop_back();
    	res.push_back({b.first,a.first});
    	res.push_back({b.second,a.second});
    }
    while(comv.size() >= 2)
    {
    	pss a = comv.back();comv.pop_back();
    	pss b = comv.back();comv.pop_back();
    	res.push_back({a.first,b.first});
    	res.push_back({a.second,b.second});
    }
    
    cout << res.size() / 2 << endl;
    for(auto& v : res)	cout << v.first << " " << v.second << endl;
    return 0;
}

E. Product Oriented Recurrence

题目大意:定义$f_x = c^{2x-6} * f_{x-1} * f_{x-2} * f_{x - 3}$当$x \geq 4$时.现给出$f_1,f_2,f_3,c,n$求出$f_n$对$10^9+7$取模的值.

数据范围:
$4 \leq n \leq 10^{18}$
$1 \leq f_1,f_2,f_3,c \leq 10^9$

思路

这个形式非常显然应该是递推,想到递推,又看到这个数据范围已经猜到是矩阵快速幂了.不过一个问题就是这个递推只是一个乘法的形式,根本不满足矩阵快速幂里的相加.因此先考虑把式子变形:由于整个表达式是乘法递推的,如果把所有递推项按已知的元素表示的话,可以看出一些规律来:
$f_1 = c^0 * f^1_1 * f^0_2 * f^0_3$
$f_2 = c^0 * f^0_1 * f^1_2 * f^0_3$
$f_3 = c^0 * f^0_1 * f^0_2 * f^1_3$
$f_4 = c^2 * f^1_1 * f^1_2 * f^1_3$
$f_5 = c^6 * f^1_1 * f^2_2 * f^2_3$
$f_6 = c^{14} * f^2_1 * f^3_2 * f^4_3$
.......
由于说相乘的时候,幂是相加的,所以如果把这些项都用题目已知的数据表示出来,就可以发现系数之间是存在和的递推关系的.用符号化的语言表述就是,把最终的结果$f_n$也用这种方式表示出来,那么就有:$f_n = c^{w_n} * f^{x_n}_1 * f^{y_n}_2 * f^{z_n}_3$.当然你也可以用$i$下标表示任意的元素,这不重要,显然对于$x_i,y_i,z_i$这些元素来说,他的递推式是满足前三者之和的递推形式的,举个例子就是$x_i = x_{i - 1}+x_{i-2}+x_{i-3}$,其余两个也同理,关于这个系数的计算显然可以直接仿照斐波那契数列的矩阵快速幂写法求出,构造的系数矩阵比较好想,故直接给出:$\begin{vmatrix}1&1&1\\1&0&0\\0&1&0\end{vmatrix}$
而$x,y,z$的初始矩阵也比较明显,就是前三位看谁是$1$就行了,这里不再提这个了.
比较麻烦的是$w_i$的式子,显然$w_i = w_{i-1}+w_{i-2}+w_{i-3}+2i-6$由于存在一个多余的数$2i-6$就使得他的计算要不同一些,如果要直接构造矩阵也不是不可以,但是会比较麻烦,这里可以继续从性质出发,因为$2i-6$这个形式是非常特殊的,如果要和整个式子联系起来,不难想到$i-1+i-2+i-3=3i-6$,只比他多一个$i$.那么现在定义$g_i=w_i+i$的话,原来的式子里就可以替换成$w_i=g_{i-1}+g_{i-2}+g_{i-3}-i$把多余的一个$i$移到左边,恰好就得到了一个完整的递推式,即$g_i=g_{i-1}+g_{i-2}+g_{i-3}$.这个显然和上面的递推式是一样的,系数矩阵可以沿用下来,但是最后的答案要额外的减掉一个$n$这一点要额外注意.
那么显然,最后要求的就是$w_n,x_n,y_n,z_n$,由于他们的系数矩阵都是一样的,所以对系数矩阵$A$求一次快速幂,即求$A^{n-3}$(你只需要自乘$n-3$次就可以得到答案了).再让四个元素的初始矩阵分别做矩阵乘法得到各自的答案,再额外的处理得到真实的$w_n$就可以做出这道题了.

超时代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7,MOD = 1e9+7;
struct mat
{
	ll m[N][N];
}a,res,x,y,z,g;
mat mul(mat A,mat B,int len)
{
    mat c;
    memset(c.m,0,sizeof c.m);
    for(ll i = 1;i <= len;++i)
        for(ll j = 1;j <= len;++j)
            for(ll k = 1;k <= len;++k)
            {
            	c.m[i][j]=(c.m[i][j]+(A.m[i][k]*B.m[k][j])%MOD)%MOD;
            }
	return c;
}
ll qpow(ll a,ll b)
{
	ll res = 1 % MOD;
	while(b)
	{
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void matrixqpow(ll len,ll k)
{
	memset(res.m,0,sizeof res.m);
	for(int i = 1;i <= len;++i)	res.m[i][i] = 1;
    while(k)
    {
        if(k & 1)   res = mul(res,a,len);
        a = mul(a,a,len);
        k >>= 1;
    }
}
int main()
{
	ll n,f1,f2,f3,c;cin >> n >> f1 >> f2 >> f3 >> c;
	// build a
	a.m[1][1] = a.m[1][2] = a.m[1][3] = 1;
	a.m[2][1] = 1;a.m[2][2] = a.m[2][3] = 0;
	a.m[3][1] = 0;a.m[3][2] = 1;a.m[3][3] = 0;
	//build x
	x.m[1][1] = x.m[2][1] = 0;x.m[3][1] = 1;
	//build y
	y.m[1][1] = 0;y.m[2][1] = 1;y.m[3][1] = 0;
	//build z
	z.m[1][1] = 1;z.m[2][1] = z.m[3][1] = 0;
	//build g
	g.m[1][1] = 3;g.m[2][1] = 2;g.m[3][1] = 1;
	
	// gain final factor
	
	// gain A^(n-2)     res = A^(n-2)
	matrixqpow(3,n - 3);
	// gain w,x,y,z
	ll fnlw = mul(res,g,3).m[1][1] - n;
	ll fnlx = mul(res,x,3).m[1][1];
	ll fnly = mul(res,y,3).m[1][1];
	ll fnlz = mul(res,z,3).m[1][1];
	ll res = 1;
	// cout << fnlw << " " << fnlx << " " << fnly << " " << fnlz << " " << endl;
	res = (res * qpow(c,fnlw) % MOD) % MOD;
	res = (res * qpow(f1,fnlx) % MOD) % MOD;
	res = (res * qpow(f2,fnly) % MOD) % MOD;
	res = (res * qpow(f3,fnlz) % MOD) % MOD;
	cout << res;
}

超时

但是这样就会喜闻乐见的$TLE at 4$.
经过排查,可以发现在计算最后的答案的快速幂之前一切都显得非常正常,一进去就死了,这说明快速幂里面出现了死循环,再调试可以发现是因为幂算出来可能是一个负数,因为$w_n$涉及到了减法操作,如果不对$w_n$特殊处理就会导致快速幂的幂是一个负数,最后就会死循环了.
好继续,你觉得给有负数的套一个负数取模,对$fnlw$模到正数,问题就会解决了.然而这样之后还是错的,不光答案错了,大样例还是$TLE$.说明方向错了.
那为什么错了,原因就在于简单的去$mod$调整这个质数并不是同余的.这样直接的同余只有乘加减可以这么干,这里是幂形式,根本不能直接这么干.
正确操作是一种叫欧拉降幂的操作,要用到拓展欧拉定理的一个特殊情况,简单来说,在$gcd(a,p)=1$的前提下有$a^b\equiv a^{b\%\phi(p)}(mod p)$显然根据欧拉函数$\phi(x)$的定义有:当$x$是质数的时候,所有比$x$小的数都应该与之互质,因此$\phi(x)=x-1$,即对于$fnlw$来说应该对$10^9+6$取模而不是$10^9+7$.在这样处理之后便可以解决这道题目.
关于欧拉降幂,可以学习一下他的通用情况,这里只是互质的一种情况,其余的就不展开了.

代码

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7,MOD = 1e9+7,phip = 1e9+6;
struct mat
{
	ll m[N][N];
}a,res,x,y,z,g;
mat mul(mat A,mat B,int len)
{
    mat c;
    memset(c.m,0,sizeof c.m);
    for(ll i = 1;i <= len;++i)
        for(ll j = 1;j <= len;++j)
            for(ll k = 1;k <= len;++k)
            {
            	c.m[i][j]=(c.m[i][j]+(A.m[i][k]*B.m[k][j]))%phip;
            }
	return c;
}
ll qpow(ll a,ll b)
{
	ll res = 1 % MOD;
	while(b)
	{
		if(b & 1)	res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}
void matrixqpow(ll len,ll k)
{
	memset(res.m,0,sizeof res.m);
	for(int i = 1;i <= len;++i)	res.m[i][i] = 1;
    while(k)
    {
        if(k & 1)   res = mul(res,a,len);
        a = mul(a,a,len);
        k >>= 1;
    }
}
int main()
{
	ll n,f1,f2,f3,c;cin >> n >> f1 >> f2 >> f3 >> c;
	// build a
	a.m[1][1] = a.m[1][2] = a.m[1][3] = 1;
	a.m[2][1] = 1;a.m[2][2] = a.m[2][3] = 0;
	a.m[3][1] = 0;a.m[3][2] = 1;a.m[3][3] = 0;
	//build x
	x.m[1][1] = x.m[2][1] = 0;x.m[3][1] = 1;
	//build y
	y.m[1][1] = 0;y.m[2][1] = 1;y.m[3][1] = 0;
	//build z
	z.m[1][1] = 1;z.m[2][1] = z.m[3][1] = 0;
	//build g
	g.m[1][1] = 3;g.m[2][1] = 2;g.m[3][1] = 1;
	
	// gain final factor
	
	// gain A^(n-2)     res = A^(n-2)
	matrixqpow(3,n - 3);
	// gain w,x,y,z
	ll fnlw = mul(res,g,3).m[1][1] - n;
	ll fnlx = mul(res,x,3).m[1][1];
	ll fnly = mul(res,y,3).m[1][1];
	ll fnlz = mul(res,z,3).m[1][1];
	ll res = 1;
	// cout << fnlw << " " << fnlx << " " << fnly << " " << fnlz << " " << endl;
	res = (res * qpow(c,(fnlw % phip + phip) % phip)) % MOD;
	res = (res * qpow(f1,(fnlx % phip + phip) % phip)) % MOD;
	res = (res * qpow(f2,(fnly % phip + phip) % phip)) % MOD;
	res = (res * qpow(f3,(fnlz % phip + phip) % phip)) % MOD;
	cout << res;
}